bonsoon's blog |
| latest | about | random
# Cantor theorem. For any set $A$, there is no surjection from $A$ to its power set $P(A)$. $\blacktriangleright$ Indeed, take a function $f: A \to P(A)$. Consider the set $B = \{ x \in A : x \not\in f(x)\}$. Suppose $t \in A$ is such that $f(t) = B$. If $t \in B$, then $t \not \in f(t) = B$, a contradiction. If $t \not\in B$ then $t\not\in f(t)$, and hence $t\in B$, also a contradiction. Hence $B$ is not in the image of $f$, and $f$ is not surjective. $\blacksquare$ This shows that for any set, there is always a set "strictly larger than it", and taking its power set would do. Note here we adopt naive set theory, and the principle of comprehension -- that a subset exists by defining a property of a set, to assert the existence of the set $B$.